package algorithmTopics.stack;

import java.util.PriorityQueue;

/**
 * 中值搜索器
 *
 * @author 86155
 * @date 2025/07/21
 */
class MedianFinder {
    /**
     * 最小堆
     */
    private final PriorityQueue<Integer> right = new PriorityQueue<>();
    /**
     * 最大堆
     */
    private final PriorityQueue<Integer> left = new PriorityQueue<>((a, b) -> b - a);

    public MedianFinder() {

    }

    public void addNum(int num) {
        // 把添加进来的数字分为两部分保存
        //保持左右数量均衡，且左边最大 <= 右边最小,整体递增
        //左边数量至多比右边多一个
        if (left.size() == right.size()) {
            right.add(num);
            left.add(right.poll());
        } else {
            left.add(num);
            right.add(left.poll());
        }

    }

    public double findMedian() {
        if (left.size() != right.size()) {
            return left.peek();
        }
        // 注意是2.0 转化为double
        return (left.peek() + right.peek()) / 2.0;
    }
}